package sword.chapter4LinkList;

/**
 * 展平多级双向链表
 *
 * 1 2 3 4
 *   |
 *   5 6 7
 *     |
 *     8 9
 *
 * 1. 递归获取最后节点
 *
 * 存在node.child进行如下操作
 *    node遇node.next 断开
 *    node.next 链接 node.child
 *    node.child.next 链接 node.next
 *
 * 细节
 *    将node.child置null
 *    last移动到childLast
 *
 *
 * @author K
 * @date 2021-11-29 22:30
 */
public class S28Flatten {
    public static Node flatten(Node head) {
        dfs(head);
        return head;
    }

    public static Node dfs(Node node) {
        Node cur = node;
        // 记录链表的最后一个节点
        Node last = null;

        while (cur != null) {
            Node next = cur.next;
            //  如果有子节点，那么首先处理子节点
            if (cur.child != null) {
                Node childLast = dfs(cur.child);

                //  将 node 与 child 相连
                cur.next = cur.child;
                cur.child.prev = cur;

                //  如果 next 不为空，就将 last 与 next 相连
                if (next != null) {
                    childLast.next = next;
                    next.prev = childLast;
                }

                // 将 child 置为空
                cur.child = null;
                last = childLast;
            } else {
                last = cur;
            }
            cur = next;
        }
        return last;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        node1.next=node2;
        node2.prev = node1;
        node2.next=node3;
        node3.prev=node2;
        node3.next=node4;
        node4.prev = node3;

        node5.next=node6;
        node6.prev = node5;
        node6.next=node7;
        node7.prev = node6;

        node8.next=node9;
        node9.prev = node8;

        node2.child=node5;
        node6.child=node8;

        Node result = flatten(node1);
        System.out.println();
    }
}


class Node {
    public int key;
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    Node(int val) {
        this.val = val;
    }

    Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}